#include <iostream>
#include <vector>
#include <cmath>
#include <cstdint>
using namespace std;

int get(int s, int i)
{
	int bit = pow(3, i);
	return s / bit % 3;
}

int set(int s, int i, int v)
{
	int bit = pow(3, i);
	return s - get(s, i) * bit + v * bit;
}

int cal(vector<vector<int>> &grid, vector<int> &complete, int u, int s, vector<vector<int>> &dp)
{
	int n = grid.size();
	if (complete[s]) {
		return 0;
	}

	if (u == n) {
		return INT32_MAX;
	}

	if (dp[u][s] != -1) {
		return dp[u][s];
	}

	int ans = INT32_MAX;
	int cur = 0;
	for (int i = 0; i < n; i++) {
		int cost = grid[u][i];
		if (cost == INT32_MAX) {
			continue;
		}
		int t = get(s, i);
		if (t == 2) {
			continue;
		}
		cur = cal(grid, complete, i, set(s, i, t + 1), dp);
		if (cur == INT32_MAX) {
			continue;
		}
		ans = min(ans, cost + cur);
	}
	return dp[u][s] = ans;
}

void dfs(int i, int bit, int s, vector<int> &status, int n)
{
	if (i == n) {
		status[s] = 1;
	} else {
		dfs(i + 1, bit * 3, s + bit, status, n);
		dfs(i + 1, bit * 3, s + bit * 2, status, n);
	}
}

int main()
{
	int n, m;
	while (cin >> n >> m) {
		vector<vector<int>> grid(n, vector<int>(n, INT32_MAX));
		vector<vector<int>> dp(n, vector<int>(pow(3, n + 1), -1));
		vector<int> complete(pow(3, n + 1), 0);
		dfs(0, 1, 0, complete, n);

		for (int i = 0; i < m; i++) {
			int x, y, z;
			cin >> x >> y >> z;
			x--;
			y--;
			if (z < grid[x][y]) {
				grid[x][y] = z;
				grid[y][x] = z;
			}
		}
		int ans = INT32_MAX;
		for (int i = 0; i < n; i++) {
			ans = min(ans, cal(grid, complete, i, set(0, i, 1), dp));
		}
		if (ans == INT32_MAX) {
			cout << -1 << endl;
			continue;
		}
		cout << ans << endl;
	}
	return 0;
}